package recursion;

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int i = recursionBinarySearch(arr, target, 0, arr.length - 1);
        return i;
    }

    /**
     * 遍历二分算法
     * @param arr arr数组
     * @param target 查找目标
     * @param low 0
     * @param high arr.length-1
     * @return 返回目标索引 无则返回null
     */
    private static int recursionBinarySearch(int[] arr, int target, int low, int high) {
        if (low > high) {
            return -1;
        }
        int mid = (low + high) >>> 1;
        int midVal = arr[mid];
        if (target < midVal) {
            return recursionBinarySearch(arr, target, low, mid - 1);
        } else if (midVal < target) {
            return recursionBinarySearch(arr, target, mid + 1, high);
        } else {
            return mid;
        }
    }


}
